/*
 * @lc app=leetcode.cn id=39 lang=typescript
 *
 * [39] 组合总和
 */

// @lc code=start
function combinationSum(candidates: number[], target: number): number[][] {
  const temp = [];
  const ans = [];
  const backtrack = (idx: number, target: number): void => {
    if (target < 0) return;
    if (target === 0) {
      ans.push([...temp]);
      return;
    }
    if (idx === candidates.length) return;
    // 不选择当前数字
    backtrack(idx + 1, target);
    // 选择当前数字
    temp.push(candidates[idx]);
    // 选择当前数字后，继续递归找target剩余的数字
    backtrack(idx, target - candidates[idx]);
    // 回溯
    temp.pop();
    return;
  };

  backtrack(0, target);

  return ans;
}
// @lc code=end
